package day01.归并算法;


import java.io.IOException;
import java.util.List;
import java.util.PriorityQueue;

/**
 * @author wangxi created on 2023/10/14 23:09
 * @version v1.0
 *
 *  K 路合并
 *
 * 首先用一个最小堆来维护K个指针，每次从堆中取最小值，开销为logK，最多从堆中取N次元素。
 *  因为时间复杂度为 NlogK
 *
 *  有一类排序算法叫做归并排序，里面就有大家熟知的两路归并实现。现在相当于K路归并，因此可以拓展一下，思路类似。
 *  对每个文件设计一个指针，取出K个指针中数值最小的一个，
 *  然后把最小的那个指针后移，接着继续找K个指针中数值最小的一个，继续后移指针……直到N个文件全部读完为止
 */
public class KMergeSort {
    public interface FileReader {
        //true to indicate the file still has some data, false means EOF.
        boolean hasNext() throws IOException;

        //Read the next value from file, and move the file read offset.
        int next() throws IOException;
    }

    public interface FileWriter {
        void append(int value) throws IOException;
    }

    public void kMergeSort(final List<FileReader> readers, FileWriter writer)
            throws IOException {
        PriorityQueue<Pair<FileReader, Integer>> heap =
                new PriorityQueue<>((p1, p2) -> p1.getValue() - p2.getValue());
        for (FileReader fr : readers) {
            if (fr.hasNext()) {
                heap.add(new Pair<>(fr, fr.next()));
            }
        }
        while (!heap.isEmpty()) {
            Pair<FileReader, Integer> current = heap.poll();
            writer.append(current.getValue());
            FileReader currentReader = current.getKey();
            if (currentReader.hasNext()) {
                heap.add(new Pair<>(currentReader, currentReader.next()));
            }
        }
    }
}
